A network processor generally controls the flow of packets between a physical transmission medium, such as a physical layer portion of, e.g., an asynchronous transfer mode (ATM) network or synchronous optical network (SONET), and a switch fabric in a router or other type of packet switch. Such routers and switches generally include multiple network processors, e.g., arranged in the form of an array of line or port cards with one or more of the processors associated with each of the cards.
Packets in the routing and switching context are also commonly referred to as PDUs, and are typically variable in size. However, a switch fabric is often configured to process data only in fixed-size units, commonly referred to as cells. A given PDU received at an ingress line card of a router or switch is therefore processed, under the control of a network processor, to separate it into cells suitable for processing in the switch fabric.
In order to keep track of which cells are associated with which PDUs, a linked list approach is typically used in which head and tail pointers are stored for each PDU being processed. The head pointer identifies in a data buffer the particular block that stores a first cell of the PDU. Similarly, the tail pointer identifies in the data buffer the particular block that stores a final cell of the PDU. The data buffer blocks are typically linked such that an entire PDU as stored in the data buffer is identifiable using only the head and tail pointers.
It is often the case that a given PDU may be of a sufficiently small size that it can be processed in its entirety as a single cell. Such PDUs are referred to herein as “single-cell PDUs.”
Conventional network processors generally process single-cell PDUs using the same linked list approach described above in the context of multiple-cell PDUs. In the case of a single-cell PDU, its head pointer and tail pointer both identify the same block in the data buffer. This leads to a number of significant problems relating to memory access. For example, when handling a large number of single-cell PDUs, the number of required linked list read and write operations is substantially increased, which degrades the overall throughput performance of the network processor. In addition, when a memory external to the network processor is utilized to maintain the linked list, an increase in the number of single-cell PDUs increases the latency associated with accessing the external memory, due to limitations in the available bus bandwidth. Generally, the ratio of linked list memory access cycles to data buffer memory access cycles increases substantially as the number of single-cell PDUs being processed increases, thereby degrading network processor performance. As a result, most conventional network processors have difficulty handling small PDUs at a specified line rate.
Accordingly, a need exists for a network processor or other type of processor that is capable of efficiently processing single-cell PDUs, without the above-noted problems associated with conventional techniques.